public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {7, 5, 11, 2, 4, 6, 9, 1, 8, 3};
        System.out.println("排序前：");
        print(arr);

        quickSort(arr);
        System.out.println("排序后：");
        print(arr);
    }

    public static void quickSort(int[] arr) {
        if (arr == null || arr.length <= 1) return;
        quickSort(arr, 0, arr.length);
    }

    private static void quickSort(int[] arr, int low, int high) {
        if (high - low <= 1)    return;

        // 分区。
        int partition = partition(arr, low, high);

        // 递归左右两个分区。
        quickSort(arr, low, partition);
        quickSort(arr, partition + 1, high);
    }

    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[low];
        int left = low;
        int right = high - 1;

        while (left < right) {
            while (left < right && arr[right] >= pivot) {
                right--;
            }
            arr[left] = arr[right];

            while (left < right && arr[left] <= pivot) {
                left++;
            }
            arr[right] = arr[left];
        }

        arr[left] = pivot;

        return left;
    }


    public static void print(int[] arr) {
        if (arr == null) return;
        for(int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
}